/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/find-the-missing-number-ii
   @Language: C++
   @Datetime: 19-06-05 10:23
   */

class Solution {
	int dfs(int n, string &str, int pos, bool nums[]){
		if(pos==str.length()){
			int num=-1, cnt=0;
			for(int i=1; i<=n; ++i){
				if(nums[i]) continue;
				++cnt;
				num=i;
			}
			return cnt==1?num:-1;
		}
		if(str[pos]=='0') return -1;
		for(int i=1; i<3 && pos+i<=str.length(); ++i){
			int t=stoi(str.substr(pos,i));
			if(t>n || nums[t]) continue;
			nums[t]=true;
			int num=dfs(n,str,pos+i,nums);
			if(num!=-1) return num;
			nums[t]=false;
		}
		return -1;
	}
public:
	/**
	 * @param n: An integer
	 * @param str: a string with number from 1-n in random order and miss one number
	 * @return: An integer
	 */
	int findMissing2(int n, string &str) {
		// write your code here
		bool nums[31]={false};
		return dfs(n,str,0,nums);
	}
};
